Изоморфизм графов
Изоморфизм графов
Определение:
Графы $G_1 = (V_1, E_1)$ и $G_2 = (V_2, E_2)$ называются **изоморфными**, если существует биекция $f: V_1 \to V_2$ такая что: $$v_1v_2 \in E_1 \iff f(v_1)f(v_2) \in E_2$$
Свойства изоморфизма графов
Формулировка:
При изоморфизме сохраняются степени вершин. Цикл переходит в цикл такой же длины.